﻿// 3621. 判断素数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
/*
https://www.acwing.com/problem/content/3624/

输入一个整数，判断该整数是否为素数，若是，输出该整数，若否，输出大于该整数的第一个素数。
（例如，输入为 14，输出 17，因为 17 是大于 14的第一个素数）

输入格式
一个整数 n。

输出格式
按要求输出答案。

数据范围 
1≤n≤10000
输入样例：
14
输出样例：
17
*/

const int N = 20000;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (st[i]) continue;
        primes[cnt++] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

int main()
{
    get_primes(15000);
    int n;
    cin >> n;
    int l = 0; int r = cnt-1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (primes[mid] >= n) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }

    cout << primes[l] << endl;
    return 0;
}
 